package org.xqh.study.leetcode.algorithm.studyplan;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName DictTree2
 * @Description 他人提交答案
 *
 * https://leetcode-cn.com/problems/word-search-ii/
 * @Author xuqianghui
 * @Date 2021/3/7 17:13
 * @Version 1.0
 */
public class DictTree2 {

    public List<String> findWords(char[][] board, String[] words) {
        int n = board.length, m = board[0].length;
        List<String> ans = new ArrayList<>();

        for(String s:words){
            char[] cs = s.toCharArray();
            loop:for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(dfs(board, i, j, cs, 0)) {
                        ans.add(s);
                        break loop;
                    }
                }

            }
        }
        return ans;
    }

    int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};

    public boolean dfs(char[][] board, int x, int y, char[] cs, int u){
        if(cs[u] != board[x][y]) return false;
        if(u == cs.length - 1) return true;

        char c = board[x][y];
        board[x][y] = '.';

        for(int i = 0; i < 4; i++){
            int sx = x + dx[i], sy = y + dy[i];

            if(sx < 0 || sx >= board.length || sy < 0 || sy >= board[0].length || board[sx][sy] == '.') continue;

            if(dfs(board, sx, sy, cs, u + 1)) {
                board[x][y] = c;
                return true;
            }
        }

        board[x][y] = c;
        return false;

    }
}
